package com.yangzhe.algorithm.c022;

import java.io.*;

/**
 * 小和问题
 * 测试链接 : https://www.nowcoder.com/practice/edfe05a1d45c4ea89101d936cac32469
 * 提交以下的code，提交时请把类名改成"Main"，可以直接通过
 */
public class Code01_SmallSum1 {
	private static int MAX_LENGTH = 100001;

	private static int n = 0;

	private static int[] arr = new int[MAX_LENGTH];

	private static int[] help = new int[MAX_LENGTH];

	/**
     * 主函数
     */
	public static void main(String[] args) throws IOException {
		// 读取数组
		try (InputStreamReader inputStream = new InputStreamReader(System.in);
			 BufferedReader bufferedReader = new BufferedReader(inputStream);
		) {
			StreamTokenizer streamTokenizer = new StreamTokenizer(bufferedReader);
			while(streamTokenizer.nextToken() != StreamTokenizer.TT_EOF){
				n = (int)streamTokenizer.nval;

				for(int i = 0;i < n; i++) {
					streamTokenizer.nextToken();
					arr[i] = (int)streamTokenizer.nval;
				}
			}
		}

		try (OutputStreamWriter out = new OutputStreamWriter(System.out);
			 PrintWriter printWriter = new PrintWriter(out)
		) {
			printWriter.println(smallSum(0, n - 1));
			printWriter.flush();
		}
	}

	/**
	 * 归并分治
	 * 归并排序并计算小和
	 */
	public static long smallSum(int l, int r) {
		// base case:范围只有一个数的时候，小和一定是0
		if (l == r) {
			return 0;
		}
		int m = (l + r) / 2;
		// 小和等于左侧的小和 + 右侧的小和 + 跨左右的小和
		return smallSum(l, m) + smallSum(m + 1, r) + merge(l, m ,r);
	}

	/**
     * 归并排序合并左右两边数组，并计算小和
     * @param l 左边界
     * @param m 中间
     * @param r 右边界
     * @return 小和
     */
	public static long merge(int l, int m, int r) {
		int lIndex = l;
		int rIndex = m + 1;
		// 这里使用long，避免整数过大溢出，这里是题目经常设置的坑
		long preSum = 0;
		long smallSum = 0;
		// 1. 计算跨左右的小和，此时左侧和右侧已经再上一个迭代中变得有序
		for (; rIndex <=r; rIndex++) {
			// 左侧比右侧小则累加
			// lIndex只向右移动，preSum会记录已经累加过的数字，不再重复累加
			while(lIndex <= m && arr[lIndex] <= arr[rIndex]) {
				preSum += arr[lIndex++];
			}
			smallSum += preSum;
		}


		// 2. merge数组
		lIndex = l;
		rIndex = m + 1;
		int hIndex = l;
		// 2.1 将左右两边数copy到help数组中，哪边小先copy哪边
		while(lIndex <= m && rIndex <= r) {
			help[hIndex++] = arr[lIndex] <= arr[rIndex] ? arr[lIndex++] : arr[rIndex++];
		}

		// 2.2 左边剩余的copy到help数组中
		while(lIndex <= m) {
			help[hIndex++] = arr[lIndex++];
		}

		// 2.3 右边剩余的copy到help数组中
		while(rIndex <= r) {
			help[hIndex++] = arr[rIndex++];
		}

		// 2.4 将help刷回原来的数组中
		if (r + 1 - l >= 0) System.arraycopy(help, l, arr, l, r + 1 - l);

		return smallSum;
	}
}